There are a number of known techniques for calculating the modulus of a number with respect to a constant (e.g. a mod b, where a and b are integers) in hardware logic. Such hardware logic may form part of a processor such as a CPU (Central Processing Unit) or GPU (Graphics Processing Unit). One example calculates the modulus as a by-product of an iterative division implementation (e.g. an iterative division which calculates a/b). However, where the value of ‘b’ is constant, it may be possible instead to use lookup tables and multiplexers (e.g. where a is not too large). Given the binary nature of most computer mathematics, calculations where the constant b is a power of two are trivial to perform and further, where b is a multiple of a power of 2, the calculation can be simplified by first performing the trivial division and modulus of the power of two factor and then recombining subsequently. The operation of calculating the modulus of a number with respect to a constant may be referred to as modulo (or modulus) calculation or the modulo operation.
In another known method which calculates the modulus of an n-bit number, a, with respect to an unsigned m-bit constant, b, each bit in number a, denoted a[i], is mapped to either 0 or 2imodb which gives n m-bit numbers (one for each bit in number a). The n m-bit numbers can then be added together in a logarithmic pairwise manner, with an optional subtract b (or a multiple of b) if the value of any addition is greater than b. This method is typically small (in terms of area of hardware logic required to implement it) but slow due to the use of additions and optional subtractions.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known methods of implementing modulo calculation in hardware logic.